[Related Art (1)]
The certified shuffling technology of the related art includes the invention disclosed in JP-A No. 2001-251289, for example. FIG. 1 shows an arrangement described in the above publication. In the drawings accompanying the present application, arrows that are joined together mean that all of information from the sources of the arrows are put together and sent to the destination of the arrows, and arrows that are branched mean that all or part of information from the sources of the arrows are sent to the destinations of the arrows. Re-encryption shuffle referred to in the above publication is called shuffle in the present specification.
In FIG. 1, encrypted text and public key 100 is input to shuffling step 101 where it is shuffled. Encrypted text and public key 100 that is input and shuffling information 102 which specifies the shuffling are sent to identical conversion certifying step 103, and shuffling information 102 is sent to substitution certifying step 104. Identical conversion certifying step 103 generates and outputs identical conversion certifying text 105, and at the same time sends random number 106 used to generate identical conversion certifying text 105 to substitution certifying step 104. Substitution certifying step 104 outputs substitution certifying text 107. Response generating step 108 is supplied with identical conversion certifying text 105, substitution certifying text 107, the encrypted text, public key 100, and shuffled encrypted text 109, adds a response to identical conversion certifying text 105, substitution certifying text 107, and the encrypted text to generate shuffle certifying text 110, and outputs shuffle certifying text 110.
In combination with the response, identical conversion certifying text 105 certifies that it has the knowledge of shuffling of the order of input texts and the converted contents of encrypted texts, and also that if an input encrypted text comprises elements of a plurality of integers, then each of the elements has been encrypted depending on the shuffling of the same order. In combination with the response, substitution certifying text 107 certifies that shuffling of the order of input encrypted texts has been performed properly.
The term “shuffle” shown in FIG. 1 means that the order of input encrypted texts is shuffled and they are re-encrypted. To certify that the above process is performed properly, the above document employs two certifying steps, i.e., the identical conversion certifying step and the substitution certifying step. The document achieves efficient generation of a shuffle certifying text by dividing objects to be certified.
[Related Art (2)]
The description of JP-A No. 08-263575, for example, is referred to with respect to the certified decryption technology of the related art. FIG. 2 shows an arrangement described in the above publication.
In FIG. 2, shuffled encrypted text 200 and secret key 201 are input to and decrypted by decrypting step 203. Shuffled encrypted text 200 and secret key 201 that are input and also decrypted text 204 that has been decrypted therefrom are sent to decryption certifying step 205. Decryption certifying step 205 outputs decryption certifying text 206 from these items of information.
The term “decryption” means that an encrypted text is partly decrypted using some of the secret keys that are owned discretely. The encrypted text is completely decrypted by repeating decryption using all the secret keys.
[Related Art (3)] (A Certified Shuffle-Decrypting Method of the Related Art)
A certified shuffle-decrypting method can be achieved by combining related art 1 and related art 2.
FIG. 3 shows a certified shuffle-decrypting method of the related art. The certified shuffle-decrypting method is accomplished simply by combining related art 1 and related art 2.
Encrypted text and public key 301, shuffling step 302, shuffling information 303, shuffled encrypted text 304, identical conversion certifying step 307, random number 308, identical conversion certifying text 309, substitution certifying step 310, substitution certifying text 311, response generating step 312, and shuffle certifying text 313 in FIG. 3 are identical respectively to encrypted text and public key 100, shuffling step 101, shuffling information 102, shuffled encrypted text 109, identical conversion certifying step 103, random number 106, identical conversion certifying text 105, substitution certifying step 104, substitution certifying text 107, response generating step 108, and shuffle certifying text 110 in FIG. 1. Secret key 300, shuffled encrypted text 304, decrypting step 305, decrypted text 306, decryption certifying step 314, and decryption certifying text 315 in FIG. 3 are identical respectively with secret key 201, shuffled encrypted text 200, decrypting step 203, decrypted text 204, decryption certifying step 205, and decryption certifying text 206 in FIG. 2.
The method shown in FIG. 3 shows in that shuffled encrypted text 304 is included in shuffle-decrypting certifying text 316, shuffled encrypted text 304 is input to decryption certifying step 314 and is not input to response generating step 312.
[Related Art (4)]
The description of JP-A No. 2002-344445, for example, is referred to with respect to the certified shuffle-decrypting technology of the related art.
In the above publication, a shuffled encrypted text is not added to a shuffle-decrypted text. According to the invention disclosed in the above publication, an incomplete commitment of the shuffled encrypted text is added to a shuffled decrypted text. By modifying related art 1 and related art 2 for improvement, the legitimacy of shuffling and decryption can be accomplished if the commitment of the shuffled encrypted text is incomplete even when shuffled encrypted text is absent. The term “incomplete commitment” refers to a commitment wherein information of an object to be committed, i.e., the shuffled encrypted text, partly leaks. It is thus possible to attack the encryption system using the data that has leaked.